By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 31, Issue 2, pp. 331-664

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Approximating the Throughput of Multiple Machines in Real-Time Scheduling

Amotz Bar-Noy, Sudipto Guha, Joseph (Seffi) Naor, and Baruch Schieber

pp. 331-352

BibTeX  Abstract Full Text:  PDF

Low Redundancy in Static Dictionaries with Constant Query Time

Rasmus Pagh

pp. 353-363

BibTeX  Abstract Full Text:  PDF

Maintaining Minimum Spanning Forests in Dynamic Graphs

Monika R. Henzinger and Valerie King

pp. 364-374

BibTeX  Abstract Full Text:  PDF

Evolutionary Trees Can be Learned in Polynomial Time in the Two-State General Markov Model

Mary Cryan, Leslie Ann Goldberg, and Paul W. Goldberg

pp. 375-397

BibTeX  Abstract Full Text:  PDF

The Complexity of Counting in Sparse, Regular, and Planar Graphs

Salil P. Vadhan

pp. 398-427

BibTeX  Abstract Full Text:  PDF

Matchings Meeting Quotas and Their Impact on the Blow-Up Lemma

Vojtech Rödl, Andrzej Rucinski, and Michelle Wagner

pp. 428-446

BibTeX  Abstract Full Text:  PDF

Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns

Gen-Huey Chen, Ming-Yang Kao, Yuh-Dauh Lyuu, and Hsing-Kuo Wong

pp. 447-459

BibTeX  Abstract Full Text:  PDF

Quantum Formulas: A Lower Bound and Simulation

Vwani P. Roychowdhury and Farrokh Vatan

pp. 460-476

BibTeX  Abstract Full Text:  PDF

A 2-Approximation Algorithm for the Directed Multiway Cut Problem

Joseph (Seffi) Naor and Leonid Zosin

pp. 477-482

BibTeX  Abstract Full Text:  PDF

The Global Power of Additional Queries to P-Random Oracles

Wolfgang Merkle

pp. 483-495

BibTeX  Abstract Full Text:  PDF

Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems

Ketan D. Mulmuley and Milind Sohoni

pp. 496-526

BibTeX  Abstract Full Text:  PDF

On-Line Load Balancing in a Hierarchical Server Topology

Amotz Bar-Noy, Ari Freund, and Joseph (Seffi) Naor

pp. 527-549

BibTeX  Abstract Full Text:  PDF

Checking Approximate Computations of Polynomials and Functional Equations

Funda Ergün, S. Ravi Kumar, and Ronitt Rubinfeld

pp. 550-576

BibTeX  Abstract Full Text:  PDF

The Polygon Exploration Problem

Frank Hoffmann, Christian Icking, Rolf Klein, and Klaus Kriegel

pp. 577-600

BibTeX  Abstract Full Text:  PDF

On the Computational Complexity of Upward and Rectilinear Planarity Testing

Ashim Garg and Roberto Tamassia

pp. 601-625

BibTeX  Abstract Full Text:  PDF

New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning

Tom Leighton, Chi-Jen Lu, Satish Rao, and Aravind Srinivasan

pp. 626-641

BibTeX  Abstract Full Text:  PDF

Adaptive and Efficient Algorithms for Lattice Agreement and Renaming

Hagit Attiya and Arie Fouren

pp. 642-664

BibTeX  Abstract Full Text:  PDF